import java.util.*;

import javax.swing.SortingFocusTraversalPolicy;
import java.io.File;
import javax.xml.parsers.DocumentBuilderFactory;
import org.w3c.dom.Document;
import org.w3c.dom.Element;
import org.w3c.dom.NodeList;

public class Algorithm {
public static int flag=0;
public static Complex[] coefs;
public static int[] alphas;
public static int firstUse=1;
public static Integer N;
public static String File;
	public static HashSet<Integer> SFT(int N,double tau, double delta, double norm){
		double norm2 = Norm2Square(N,Math.min(100,N));//compute the norm
		
		Complex[] Q = new Complex[N];
		HashSet<Integer>[] setList;
		HashSet<Integer> unionOfB;
		int x=0;
		unionOfB = new HashSet<Integer>();
		setList = GenerateQueries(N, tau/36, norm,(10)* delta/(log2(N)*Math.pow(norm2/tau, 1.5)));
		
		for(int i = 1; i<setList.length; i++)
			unionOfB.addAll(setList[i]);
		
		for(int a : setList[0]){
			for(int b : unionOfB){
				 x= (((a-b) % N)+N)%N;
				if(Q[x]==null) {
					Q[x] = queryInFunc(x);//get value x from function
				}
			}
		}
		return fixedQuriesSFT(N, tau, setList, Q);

	}
	
	private static HashSet<Integer> fixedQuriesSFT(int N, double tau, HashSet<Integer>[] setList, Complex[] Q) {
		HashSet<HashSet<Integer>> Candidate1;
		HashSet<HashSet<Integer>>Candidate2;
		HashSet<Integer> L;
		HashSet<Integer> Cand;
		int decision;
		
		int aTag=0,bTag=0;
		L = new HashSet<Integer>();
		Candidate1 = new HashSet<HashSet<Integer>>();
		Cand = new HashSet<Integer>();
		Cand.add(0);
		Cand.add(N-1);
		Candidate1.add(Cand);
		//System.out.println("the N is"+N);
		//System.out.println("the log2 of N is"+log2(N));
		for(int l = 0; l<log2(N); l++){
			//System.out.println("-------" + l + "---------");
			Candidate2 = new HashSet<HashSet<Integer>>();
			for (HashSet<Integer> aTagbTagDualton: Candidate1) {
			      aTag = getMin(aTagbTagDualton);
			      bTag = getMax(aTagbTagDualton);
			      decision=Distinguish(aTag, (aTag+bTag)/2, tau, setList[0], setList[l+1], Q);//
				if(decision==1) {
					Cand = new HashSet<Integer>();
					Cand.add(aTag);
					Cand.add((aTag+bTag)/2);
					Candidate2.add(Cand);
				}
				decision=Distinguish((aTag+bTag)/2+1, bTag, tau, setList[0], setList[l+1], Q);
				if(decision==1) {
					Cand = new HashSet<Integer>();
					Cand.add((aTag+bTag)/2+1);
					Cand.add(bTag);
					Candidate2.add(Cand);
				}
			}
			Candidate1 = Candidate2;
		}
		//System.out.println(Candidate1.size());
		for(HashSet<Integer> s: Candidate1) {
			//System.out.println("Size: " + s.size() + " ; Min: " + getMin(s) + " ; Max: " + getMax(s));
			if((s.size()==1)&&(Distinguish(getMin(s),getMin(s),tau,setList[0],setList[setList.length-1], Q)==1))
				L.add(getMin(s));
		}
		return L;
	}
	
	private static HashSet<Integer>[] GenerateQueries(int N, double gamma, double norm, double delta) {
		double eta =Math.min(gamma,Math.min(Math.sqrt(gamma),gamma/norm));
		double tmpCoeff = Math.pow(norm/eta, 2);
		int mA = (int) ((0.00002) * Math.ceil(tmpCoeff*Math.log(1.0/delta))/Math.log(2));
		int mB = (int) ((0.0002) * Math.ceil(tmpCoeff*Math.log(norm/(delta*gamma))/Math.log(2)));
		
		
		//int mA = (int) ((0.0002)*(1/(gamma*gamma))*Math.log(1/delta)) + 1;
		//int mB = (int) (0.00002(1/(gamma*gamma))*Math.log(1/(delta*gamma))) + 1;
		HashSet<Integer>[] setList =new HashSet[2+log2(N)];
		//HashSet<Integer> A;
		//A = new HashSet<Integer>();
		System.out.println("the ma is " +mA);
		mA = Math.min(mA,N);
		System.out.println("the ma is " +mA);
		System.out.println("the mb is " +mB);
		
		setList[0] = RandomSet(N, mA);
		
		for (int i = 1; i < setList.length-1; i++) {
			setList[i] = RandomSet((int) Math.pow(2, i-1), (int) Math.min(mB, Math.pow(2, i-1)));
		}
		setList[setList.length-1]=RandomSet(N,(int)Math.min(Math.min(mB,Math.pow(2,log2(N))), N));
		
		return setList;
	}
	
	
	private static int Distinguish(Integer a, Integer b, double tau, HashSet<Integer> A, HashSet<Integer> B, Complex[] Q){
		double est = 0;
		int xMinusY;
		for (int x : A) {
			Complex temp = new Complex();
			
			for (int y : B) {
				xMinusY = (((x-y) % Q.length)+Q.length)%Q.length;
				temp.Add(Complex.Mult(Complex.Chi((a+b)/2, y,N), Q[xMinusY]));
			}
			
			est += Math.pow(Complex.Abs(temp)/B.size(),2);
		}
		est = est/A.size();

		if(est>=5*tau/36)
			return 1;
		else
			return 0;
	}
	
	private static int log2(int n){
		return (int) (Math.log(n)/Math.log(2));
	}
	

	private static double Norm2Square(int N,int numOfElementsInAprox)
	{
		double norm=0;
		HashSet<Integer> sample = RandomSet(N, numOfElementsInAprox);
		
		for (Integer x : sample) {
			norm += Math.pow(Complex.Abs(queryInFunc(x)),2);
		}
		System.out.println("the norm is"+norm/((double) numOfElementsInAprox ));
		return norm/Math.pow(((double) numOfElementsInAprox ),2);
		
	}
	
	private static Complex queryInFunc(Integer x)
	{
		double t,z;
		Complex c = new Complex();
		int xM;
		if (flag==0)//get vals on the fly
		{
		Scanner read=new Scanner(System.in);
		System.out.println("enter the real value for "+ x);
		t=read.nextDouble();
		System.out.println("enter the imaginary value for "+ x);
		z=read.nextDouble();
		return new Complex(t,z);
		}
		else//get vals from xml
		{
		   if(firstUse==1)
		   {
			   try {
			   XMLParse(N, new File(File));
			   }
			   catch (Exception e) 
			   {
				   System.out.println("Exception in XMLParse");
				   	   }
			   firstUse=0; 
		   }
		   

			for(int k = 0; k<coefs.length; k++) {
				c.Add(Complex.Mult(coefs[k], Complex.Chi(alphas[k], x,N)));//maybe xM
			}
			return c;
		   
		   
		}
	}
	
	
	
	
	private static HashSet<Integer> RandomSet(int N, int size) {//a random set of size "size" with elements from ZN
		HashSet<Integer> ret = new HashSet<Integer>();
		
		for(int i = 0; i<size; i++) {
			int rand = (int) Math.round((N-1)*Math.random());
			while(ret.contains(rand))
				rand = (rand+1)%N;
			ret.add(rand);
		}
		
		return ret;
	}
	
	private static Integer getMin(HashSet<Integer> ab){
		Iterator<Integer> iter = ab.iterator();
		Integer a,b;
		
		a = iter.next();
		if(!iter.hasNext())
			return a;
		b = iter.next();
		
		if(b<a)
			return b;
		return a;
	}
	
	private static Integer getMax(HashSet<Integer> ab){
		Iterator<Integer> iter = ab.iterator();
		Integer a,b;
		
		a = iter.next();
		if(!iter.hasNext())
			return a;
		b = iter.next();
		
		if(b>a)
			return b;
		return a;
	}
	
	public static void printList(HashSet<Integer> list){
		//System.out.println("dammmmmmmmmmmmmm");
		System.out.println("the heavy coefficients are");
		for (Integer x : list) {
			System.out.println(x);
		}
	}
	
	public static void XMLParse(int N, File file) throws Exception{
        //Complex[] vals=new Complex[N];

	Document doc = DocumentBuilderFactory.newInstance().newDocumentBuilder().parse(file);
	doc.getDocumentElement().normalize();
	String id = ((Element)doc.getElementsByTagName("functions").item(0)).getAttribute("id");
		
	NodeList funcList = doc.getElementsByTagName("function");
			

	for (int s = 0; s < funcList.getLength(); s++) {
		String fId = ((Element)funcList.item(s)).getAttribute("id");
		NodeList monList = ((Element)funcList.item(s)).getElementsByTagName("monom");
				
		if(id.equals(fId))
{
			//use = s;
		
		coefs = new Complex[monList.getLength()];
		alphas = new int[monList.getLength()];
				
		for(int r = 0; r < monList.getLength(); r++) {
			String real, image, alpha;
	
			real = ((Element)monList.item(r)).getElementsByTagName("real").item(0).
					getChildNodes().item(0).getNodeValue();
			image = ((Element)monList.item(r)).getElementsByTagName("image").item(0).
					getChildNodes().item(0).getNodeValue();
			alpha = ((Element)monList.item(r)).getElementsByTagName("alpha").item(0).
					getChildNodes().item(0).getNodeValue();
	
			coefs[r] = new Complex(Double.parseDouble(real), Double.parseDouble(image));
			alphas[r] = Integer.parseInt(alpha);
					
			//System.out.println(coefs[r] + " blah  " + alphas[r]);
		}
                 //vals=getVals(N,coefs,alphas);
				
		//this.functions = new Function(N, coefs, alphas);
}
	}
}
	

	
	public static void main(String[] args) {
		
		//Function f;
		//Complex c[] = new Complex[1];
		//int a[] = new int[1];
		HashSet<Integer> l;
		Scanner read=new Scanner(System.in);
		double tau,norm,delta;
		//c[0] = new Complex(1,-1);
		//a[0] = 3;
		//f = new Function(900, c, a);
		System.out.println("enter 0 if you want to enter values on the fly and 1 if you want to supply XML file");
		flag=read.nextInt();
		System.out.println("enter the size of the group");
		N=read.nextInt();
		System.out.println("enter the threshold");
		tau=read.nextDouble();
		System.out.println("enter max abs. value of f");
		norm=read.nextDouble();
		System.out.println("enter desired success probability");
		delta=read.nextDouble();
		
		
		
		if(flag==1)
		{
		   System.out.println("enter path to XML");
		   File=read.next();
		}
		
		
		//File="//a//home//cc//students//cs//barakark//xml//MyXMLFile.xml";
		System.out.println("SFT");
		l = Algorithm.SFT(N, tau, delta,norm);
		printList(l);
		System.out.println("DONE");
		
		
	}
}